package com.gorkr.hot100.simple;

/**
 * 买卖股票的最佳时机
 * @author gorkr
 * @date 2022/03/15 01:03
 *
 **/
public class L121 {

    // 超时
//    public int maxProfit(int[] prices) {
//        int length = prices.length;
//        int max = 0;
//        int tmp = -9;
//        for (int i = 0; i < length; i++) {
//            for (int j = i+1; j < length; j++) {
//                tmp = prices[j]-prices[i];
//                if(tmp>max){
//                    max=tmp;
//                }
//            }
//
//        }
//        return max;
//
//    }

    public int maxProfit(int[] prices) {
        int max = 0;
        int tmp = -9;
        int length = prices.length;
        int[] maxValue = new int[length+1];
        for (int i = length-1; i >=0 ; i--) {
            if(maxValue[i+1]<prices[i]){
                maxValue[i] = prices[i];
            }else {
                maxValue[i] = maxValue[i+1];
            }
        }
        for (int i = 0; i < length; i++) {
            tmp = maxValue[i] - prices[i];
            if(tmp>max){
                max=tmp;
            }
        }
        return max;
    }



}
    